Low complexity quantum private queries protocol

Private information retrieval(PIR) is an important privacy protection issue of secure multi-party computation, but the PIR protocols based on classical cryptography are vulnerable because of new technologies,such as quantum computing and cloud computing. The quantum private queries(QPQ) protocols available, however, has a high complexity and is inefficient in the face of large database. This paper, based on the QKD technology which is mature now, proposes a novel QPQ protocol utilizing the key dilution and auxiliary parameter. Only N quits are required to be sent in the quantum channel to generate the raw key, then the straight k bits in the raw key are added bitwise to dilute the raw key, and a final key is consequently obtained to encrypt the database. By flexible adjusting of auxiliary parameters θ and k, privacy is secured and the query success ratio is improved. Feasibility and performance analyses indicate that the protocol has a high success ratio in first-trial query and is easy to implement, and that the communication complexity of O(N) is achieved.     

Mímir: An open-source semantic search framework for interactive information seeking and discovery

Semantic search is gradually establishing itself as the next generation search paradigm, which meets better a wider range of information needs, as compared to traditional full-text search. At the same time, however, expanding search towards document structure and external, formal knowledge sources (e.g. LOD resources) remains challenging, especially with respect to efficiency, usability, and scalability.This paper introduces Mímir—an open-source framework for integrated semantic search over text, document structure, linguistic annotations, and formal semantic knowledge. Mímir supports complex structural queries, as well as basic keyword search.Exploratory search and sense-making are supported through information visualisation interfaces, such as co-occurrence matrices and term clouds. There is also an interactive retrieval interface, where users can save, refine, and analyse the results of a semantic search over time. The more well-studied precision-oriented information seeking searches are also well supported.The generic and extensible nature of the Mímir platform is demonstrated through three different, real-world applications, one of which required indexing and search over tens of millions of documents and fifty to hundred times as many semantic annotations. Scaling up to over 150 million documents was also accomplished, via index federation and cloud-based deployment.     

一种实用的多数据库量子信息检索协议

针对目前量子私有信息检索不能适用与云存储的多数据库问题,基于现在成熟的量子密钥分发方法,提出了一种适合在多数据库环境下,实用的量子私有信息检索协议。对于不同大小的数据库,协议可通过调节参数θ和k,在保证数据库安全及用户隐私的情况下,完成信息的检索。性能分析结果表明,协议的通信复杂度低,检索成功率高、易于实施。     

Object-oriented query language access to relational databases: A semantic framework for query translation

This research investigates and approach to query processing in a multidatabase system that uses an objectoriented model to capture the semantics of other data models. The object-oriented model is used to construct a global schema, defining an integrated view of the different schemas in the environment. The model is also used as a self-describing model to build a meta-database for storing information about the global schema. A unique aspect of this work is that the object-oriented model is used to describe the different data models of the multidatabase environment, thereby extending the meta database with semantic information about the local schemas. With the global and local schemas all represented in an object-oriented form, structural mappings between the global schema and each local schema are then easily supported. An object algebra then provides a query language for expressing global queries, using the structural mappings to translate object algebra queries into SQL queries over local relational schema. The advantage of using an object algebra is that the object-oriented database can be viewed as a blackboard for temporary storage of local data and for establishing relationships between different databases. The object algebra can be used to directly retrieve temporarily-stored data from the object-oriented database or to transparently retrieve data from local sources using the translation process described in this paper.     

具有多值约束的线性递归查询的有效计算

本文给出三个算法,分别用于把给定的右线性、左线性或左-右线性递归程序改写为一组更有效的规则.与Ullman等人的变换算法不同,本文的算法允许查询的初始约束可以是含任意多个约束元组的集合,而不必是单值的;这样,本文的算法不仅可以用于查询的求值,而且也可以用于子目标的处理.变换算法的正确性和变换后规则的有效性也在本文简略讨论.     

Peer-to-peer bichromatic reverse nearest neighbours in mobile ad-hoc networks

The increasing use of mobile communications has raised many issues of decision support and resource allocation. A crucial problem is how to solve queries of Reverse Nearest Neighbour (RNN). An RNN query returns all objects that consider the query object as their nearest neighbour. Existing methods mostly rely on a centralised base station. However, mobile P2P systems offer many benefits, including self-organisation, fault-tolerance and load-balancing. In this study, we propose and evaluate 3 distinct P2P algorithms focusing on bichromatic RNN queries, in which mobile query peers and static objects of interest are of two different categories, based on a time-out mechanism and a boundary polygon around the mobile query peers. The Brute-Force Search Algorithm provides a naive approach to exploit shared information among peers whereas two other Boundary Search Algorithms filter a number of peers involved in query processing. The algorithms are evaluated in the MiXiM simulation framework with both real and synthetic datasets. The results show the practical feasibility of the P2P approach for solving bichromatic RNN queries for mobile networks.     

一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

Automatic learners with feedback queries

Automatic classes are classes of languages for which a finite automaton can decide whether a given element is in a set given by its index. The present work studies the learnability of automatic families by automatic learners which, in each round, output a hypothesis and update a long-term memory, depending on the input datum, via an automatic function. Many variants of automatic learners are investigated: where the long-term memory is restricted to be the current hypothesis whenever this exists, cannot be of length larger than the length of the longest datum seen, or has to consist of a constant number of examples seen so far. Learnability is also studied with respect to queries which reveal information about past data or past computation history; the number of queries per round is bounded by a constant.     

面向无线认知网络的冗余感知数据消除

在无线认知网络的协作式频谱感知方案中,非授权用户（次要用户）将各自感知到的可用频谱信息转发给邻居节点,作为频谱分配的依据.而实际上,仅有部分数据影响着频谱分配的结果.无用信息的传递不仅产生了大量额外的通信开销,而且在频谱分配过程中浪费了计算资源.这种情况对于频谱资源稀缺的无线认知网络和能量有限的认知终端来说是无法接受的.因此,如何减少无用信息的传递是一个具有重大实际意义的问题.基于skyline查询处理,提出了多目标约束下skychannel查询处理方法,以减少冗余感知信息传递.其基本思想是：将数据空间划分为控制区域、被控区域和自由区域,按照信道的性能参数,将要查询的信道放入相应区域.传输时,直接忽略被控信道的信息而仅传输非被控信道的数据.在保证不影响频谱分配结果的前提下,可以大量降低网络开销,节约用户的计算资源.仿真结果显示,skychannel查询方法在节约查询时间、降低通信开销和计算开销等方面具有优势.